\clearemptydoublepages
\chapter{Problématique}
\label{Problematique}
Dans cette section, nous allons introduire la problématique en regardant quel
est le but du projet et ce qu'il apporte de nouveau. 

\paragraph{}
Dans tout système, un processeur monocœur ne peut exécuter qu'une tâche à la
fois. Par ailleurs, la problématique reste la même pour des processeurs
multicœurs, puisqu'il est rare de rencontrer un système ayant autant de cœurs
que de tâches. Il est donc nécessaire qu'un ordonnanceur choisisse quelle tâche
peut s'exécuter sur chaque cœur.

\paragraph{}
Dans un système standard (sans échéance stricte), le temps d'exécution que va mettre
une tâche pour s'exécuter ne sera pas calculé, puisque son comportement n'est
pas déterministe (un traitement de texte peut utiliser 1 seconde comme 1
jour de temps CPU) et que l'évaluation des temps pour des tâches non-répétitives
(non-périodiques) serait beaucoup trop coûteuse. 

\paragraph{}
Un système temps réel est un système ayant des dépendances temporelles strictes.
En effet, un tel système doit être capable d'exécuter une tâche avant une
certaine échéance donnée (temps réel strict). C'est pourquoi la durée maximale que
met la tâche pour s'exécuter, appelé le WCET (worst-case execution time) doit
être connu afin de pouvoir assurer l'exécution de la tâche avant son échéance.\\

Ci-dessous une tâche $T1$ s'exécutant et une tâche $T2$ qui préempte la
tâche $T1$ pour pouvoir s'exécuter avant son échéance :
\begin{figure}[h!]
\centering
\includegraphics[scale=0.9]{../Imgs/EDF.png}
% EDF.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Exemple d'utilisation du WCET et d'une échéance}
\end{figure}

\paragraph{}
En connaissant le temps maximum d'exécution d'une tâche, son échéance et son
heure d'exécution (grâce à sa période), il devient possible de calculer l'ordre
d'ordonnancement des tâches, en avance.\\
De cette façon, il est possible d'utiliser des algorithmes beaucoup plus optimum.
En effet, sans connaitre ces informations, il est nécessaire d'ordonnancer les
tâches en inspectant leur comportement dans le passé ou selon une politique de
priorité ou encore selon une politique \textit{FIFO} (première arrivée première exécutée). De plus,
de tels
algorithmes ne garantissent en rien que les échéances des tâches seront respectées.


\paragraph{}
Connaître en avance, l'utilisation du processeur, permet aussi d'adapter la fréquence du
processeur en fonction de son utilisation futur. Effectivement, sans connaître les prochaines tâches
devant s'exécuter, le processeur pourra diminuer sa fréquence uniquement lorsque les tâches ne
l'utilise pas à 100\%. C'est pourquoi, entre le moment où l'utilisation du
processeur diminue et l'instant où la fréquence du processeur diminue, le
processeur aura tourné à 100\% inutilement, le temps de la détection.
Temps de détection auquel un certain délai sera additionné.
Délai justifié par le fait que la diminution de fréquence coûte du temps, et qu'il ne serait donc
pas judicieux de baisser la fréquence du processeur pour un cycle machine
d'inactivité.\\

La figure \ref{fig:TempsDetection} nous montre un exemple avec une détection en un cycle machine
et un délais de 3.

\begin{figure}[h!]
 \centering
 \includegraphics{../Imgs/SchemaDelaisDetection.png}
 % SchemaDelaisDetection.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
 \caption{Temps pour la détection et le délais}
 \label{fig:TempsDetection}
\end{figure}
\FloatBarrier


\paragraph{}
Ce problème de délais et de détection est partiellement évitable avec un système
temps réel strict puisqu'il est possible de savoir en avance quand la tâche se
termine et donc de diminuer la fréquence du processeur à ce moment précis (ou le mettre en veille).
Partiellement, du fait que nous avons que le temps maximum de la tâche et non
son temps exacte.

\section{Diminution de la fréquence}
\paragraph{}
Dans un système temps réel, il est possible de pousser plus le loin le concept
en diminuant la fréquence du processeur même si une tâche est en cours
d'exécution et pourrait l'utiliser à 100\%.
\paragraph{}
Ainsi, si la différence entre l'échéance de la tâche
et l'heure actuelle s'avère assez grande pour pouvoir augmenter la durée de
la tâche et diminuer la fréquence du processeur, une économie notable d'énergie
pourra être faite.
\paragraph{}
En d'autres termes, le but est de minimiser la fréquence du processeur en
maximisant la durée des tâches, sous contrainte que toutes les tâches doivent
être terminées avant leurs échéances respectives. 
Le facteur d'extension de la durée de l'instance d'une tâche $T_{i}$ peut facilement être trouvé
avec la formule: $\displaystyle\frac{Echeance(T_{i}) - Debut(T_{i})} {WCET(T_{i})} $\\

En prenant en compte que la
durée des tâches ne peut être que multipliée par le diviseur de la fréquence (si
on divise la fréquence par 2 on multiplie la durée par 2 par exemple). Et
puisqu'un processeur n'a, en général, que quelques fréquences utilisables à
disposition, ceci diminue nettement les calculs à effectuer.



La figure \ref{fig:BaisseFrequence} est un exemple de minimisation de la
fréquence $f$ pour une tâche dont l'échéance $e$ est de 12 pour une durée
$d$ de 5 et le temps actuel $t$ de 1.
\begin{figure}[h!]
\centering
\includegraphics[scale=0.7]{../Imgs/SchemaBaisseFrequence.png}
% SchemaDelaisDetection.png: 431x371 pixel, 96dpi, 11.38x9.80 cm, bb=0 0 323 278
\caption{Diminution de la fréquence en augmentant la durée d'une tâche}
\label{fig:BaisseFrequence}
\end{figure}
\FloatBarrier

\paragraph{}
Il est encore nécessaire de prendre en compte la période, pour connaître l'heure
d'arrivée de la prochaine tâche. En effet, il se peut que l'instance d'une autre tâche débute avant
l'échéance de l'instance courante. Ainsi, pour connaître le temps libre à disposition de l'instance
courante, il suffit de prendre la plus petite valeur entre l'échéance absolue de l'instance courante
et l'heure d'arrivée de l'instance de la prochaine tâche à arriver. Même s'il
serait possible d'optimiser
l'algorithme en vérifiant le temps d'exécution à disposition de la tâche sur une
plus longue durée (en soustrayant le WCET de la prochaine tâche). Cependant,
ceci compliquerait fortement l'algorithme et ne sera donc pas implémenté dans le cadre de ce
projet.\\


Ci-dessous un exemple de minimisation de la fréquence $f$ pour une tâche $T1$ ayant sa première
instance $T1_{1}$ débutant à 0 et une tâche $T2$ ayant sa $12^{eme}$ instance $T2_{12}$
débutant au
temps 9 :
\begin{figure}[h!]
\centering
\includegraphics[scale=0.7]{../Imgs/SchemaBaisseFrequenceStopDebutTacheSuivante.png}
% SchemaTemspRestant.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Extension d'une tâche après réordonnancement}
\end{figure}
\FloatBarrier
\paragraph{}
Comme on peut le constater, même si l'échéance de l'instance $T1_{1}$ qui vaut 13 aurait permis
d'étendre la tâche d'un facteur de 3 : $(13 - 1) / 4$, 
puisque l'instance $T2_{12}$ débute au
temps 9, il n'est possible d'étendre l'instance $T1_{1}$ que d'un facteur de 2 : $(9 - 1) / 4$.\\
La formule pour calculer le facteur d'extension de la durée de l'instance $TC_{i}$ de la tâche
courante devient alors, avec $TP_{j}$ l'instance de la prochaine tâche à arriver  : \\
$\displaystyle\frac{ \min(Echeance(TC_{i}), Debut(TP_{j})) - Debut(TC_{i})} {WCET(TC_{i})} $
\paragraph{}
Cet algorithme existant s'appelle OTE pour One Time Extension \cite{OTE}. \\
C'est sur ce principe que l'ordonnanceur devra être modifié afin de réduire au
maximum la consommation d'énergie.

\section{Économie d'énergie}
\paragraph{}
Après avoir vu comment diminuer la fréquence, il est nécessaire maintenant de
comprendre comment une diminution de la fréquence va nous permettre d'économiser
de l'énergie.
\paragraph{}
Ceci est possible car le rapport entre la fréquence et la tension du CPU n'est
pas linéaire. En effet, la formule pour obtenir l'énergie consommée est $E
\propto \times U^{2} \times F$ où $E$ est l'énergie en joule, U la tension
électrique en volt appliquée au processeur et $F$ la fréquence en hertz du processeur. Cependant,
d'autres processeurs ont un exposant plus petit pour la tension, sans toutefois arriver à un
exposant de 1. Il est donc sûr d'économiser de l'énergie.\\ 

Ci-dessous, la courbe du rapport entre la puissance et la tension, en
considérant, pour cet exemple que $F \propto U$ ce qui n'est en réalité pas tout
à fait le cas, comme nous le verrons plus tard.
\begin{figure}[h!]
\centering
\includegraphics[scale = 0.2]{../Imgs/SchemaVoltEnergie.png}
% SchemaVoltEnergie.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Courbe du rapport entre tension et puissance}
\label{fig:CourbeRapportTensionEnergie}
\end{figure}
\FloatBarrier

\paragraph{}
Comme l'indique la formule, l'énergie est proportionnelle au carré de la
tension. Les tensions minimales permettant de faire fonctionner le CPU à une
fréquence donnée sont fournies par le fabriquant. Le graphique obtenu n'est pas
tout a fait linéaire mais s'en approche. Pour s'en convaincre, voici le graphique
du rapport tension et fréquence du processeur Intel® Pentium® M, dont les
valeurs sont disponibles dans sa documentation technique \cite{IntelDatasheet}.
\begin{figure}[h!]
\centering
\includegraphics[scale=0.6]{../Imgs/TensionFrequenceIntel.png}
% TensionFrequenceIntel.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Rapport tension fréquence du processeur Intel Pentium M}
\label{fig:RapportTensionFréquence}
\end{figure}
\FloatBarrier
Pour ce processeur, comme on peut le voir sur le graphique, la pente est de 2.
Nous reprendrons cette pente pour les exemples suivants.

\subsection{Fréquence maximum et veille}
\paragraph{}
Une des techniques souvent utilisée pour économiser de l'énergie est d'exécuter la tâche avec le
CPU
fonctionnant à sa fréquence maximum puis, de mettre en veille le processeur
dès la fin de  la tâche. En utilisant une tâche avec une durée
d'exécution de $t$ pour la fréquence maximum du CPU $f$ et un temps à
disposition de $2 \times t$, nous avons donc l'énergie maximum $e$ ($= u^{2} \times f$)
utilisée pendant un temps $t$ et une énergie presque nulle, le reste du
temps.\\

Nous obtenons donc une consommation total d'énergie de : $e + 0 = e$.
\begin{figure}[h!]
\centering
\includegraphics[scale=0.2]{../Imgs/StopEnergie.png}
% StopEnergie.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\label{fig:Énergie consommée avec fréquence max et veille}
\end{figure}
\FloatBarrier

\subsection{OTE}
\paragraph{}
En utilisant OTE, et en supposant que nous pouvons diviser la fréquence par 2, il devient possible
d'exécuter la
tâche sur les 2 unités de temps à disposition. Ainsi nous pouvons diviser par 1.5 la tension $u$,
selon la pente de 2, trouvée précédemment. Et
puisque le rapport entre la tension et l'énergie est au carré, selon la formule
$E = U^{2} \times F$, en divisant par 1.5 la tension, nous divisons par
$1.5^{2}$ l'énergie utilisée et nous obtenons, de cette façon, une énergie $e2 =
\displaystyle(\frac{u}{1.5})^{2} \times \displaystyle\frac{f}{2}  =>  e2 = \displaystyle\frac{u^{2}
\times f}{4.5} = \frac
e{4.5}$\\

Nous obtenons donc approximativement une énergie totale de : $\displaystyle\frac{e}{4.5} +
\frac{e}{4.5}
= \frac{e}{2.25}$.
\begin{figure}[h!]
\centering
\includegraphics[scale=0.3]{../Imgs/EnergieOTE.png}
% EnergieOTE.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\label{fig:Énergie consommée avec OTE}
\end{figure}
\FloatBarrier
\paragraph{}
Nous avons donc un gain de 2.25 si nous utilisons OTE sur ce type de processeur.
À noter qu'il faut pouvoir allonger la tâche ce qui ne sera pas le cas en
permanence (dépend du nombre de tâches et de la fréquence maximum du processeur). 

La formule du calcul de la consommation d'énergie a été tirée de
\cite{ReducedEnergyScheduling} et les explications de
\cite{ClaudeEvequoz:Professor}.

\section{Ordonnanceur des RT Linux}
\paragraph{}
Afin de pouvoir ordonnancer les instances des tâches d'un système périodique, l'ordonnanceur doit
posséder plusieurs informations tels que les files des tâches et les priorités des tâches, entre
autres. Cette section offre un survol de ces différents points.

\subsection{Files}
\paragraph{}
Un système temps réel périodique nécessite 2 files. La première, est la file des éligibles dans
laquelle se trouvent les tâches prêtes à être exécutées et qui sont généralement triées par priorité
afin d'exécuter rapidement la tâche la plus prioritaire, en tête de file.
\label{file}
\paragraph{}
En général, comme dans Xenomai, ce type de file est plutôt représentée sous forme d'une liste (ou
tableau) de files correspondant aux priorités du systèmes. Ceci permet une gestion facilitée et plus
rapide puisque pour insérer une tâche de priorité n, il suffit d'insérer en queue de la file n
plutôt que de devoir effectuer un tri à l'insertion ou à l'extraction dans une file simple. On
obtient donc une complexité à l'extraction comme à l'insertion en $O(1)$. À noter tout de même que
cette façon de faire utilise plus de mémoire qu'une simple file de priorité. Pour cette raison,
certains systèmes nécessitant une utilisation mémoire réduite, comme ZottaOS, préféreront une
file simple, même si celle-ci augmentera la complexité d'insertion ou d'extraction en $O(log(n))$
pour les meilleures algorithmes de tri.


Ci-dessous un exemple d'une file prioritaire de files avec traitement des égalités FIFO
(une file par
priorité) :

\begin{figure}[h!]
\centering
\includegraphics[scale=0.8]{../Imgs/SchemaFifo.png}
% SchemaFifo.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Schéma de l'ordonnancement prioritaire avec traitement des égalités FIFO}
\label{fig:SchemaFifo}
\end{figure}
\FloatBarrier

\paragraph{}
La 2ème, la file des arrivées, est triée par
ordre croissant selon la date de la prochaine arrivée des instances des
tâches. La
première instance dans cette file sera la prochaine instance à arriver.
Ainsi lorsque le timer se déclenche, le système n'aura plus qu'à récupérer la première
instance de cette file et la placer dans la liste des éligibles.

\subsection{Priorité}
\paragraph{}
Dans la section précédente, nous avons parlé de systèmes temps réel strict
possédant pour chaque tâche une échéance, un WCET et une période. Toutefois,
comme nous avons pu l'entrevoir, d'autres systèmes temps réel strict, comme
Xenomai, fonctionnent en interne, uniquement avec la notion de période et de priorité.\\
Dans Xenomai, les priorités sont fixées statiquement à la compilation. Ces dernières sont
généralement fixées, par l'utilisateur, de façon inversement proportionnelles aux durées des tâches.
Ainsi pour les tâches $T1$ et $T2$ les prédicats suivant doivent être vrai :
$WCET(T1)< WCET(T2) \Leftrightarrow prio(T1) > prio(T2)$ 
et
$WCET(T1) => WCET(T2) \Leftrightarrow prio(T1) <= prio(T2)$ 

Notons que l'égalité peut se trouver dans le premier comme dans le deuxième prédicat. 

\subsection{Échéance}
\paragraph{}
L'échéance d'une tâche peut quant à elle être déterminée de façon à respecter certaines contraintes,
ou alors, il est possible de simplement désirer que l'instance courante d'une tâche doit se terminer
avant que la prochaine instance de cette tâche débute. Ce cas particulier ou l'échéance est
égale à la période existe
dans l'algorithme connu sous le nom de RM (Rate Monotonic) \cite{RM:website}, que nous utiliserons
dans ce projet.

Ci-dessous un exemple pour une tâche $T1$ qui a comme échéance sa période :
\begin{figure}[h!]
\centering
\includegraphics{../Imgs/RM.png}
% RM.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{RM avec: Échéance = Période}
\end{figure}

\paragraph{}
Ajoutons que l'utilisateur se devra de s'assurer que le système est bien ordonnançable en
vérifiant si les échéances des tâches sont bien respectées. En cas contraire, les échéances et donc
les périodes, devront être revues ou du matériel plus rapide devra être installé.

\subsection{Temps d'exécution restant}
\label{TempsRestant}
\paragraph{}
Il reste toutefois encore un problème, imaginons le cas d'une tâche $T1$ ayant
une durée de 4 et qui a une instance démarrant au temps 0. Ainsi que l'instance d'une tâche $T2$
arrivant au temps 2. Lorsque la tâche $T1$ est ordonnancée, nous allons appliquer l'algorithme OTE.
Nous allons donc commencer par vérifier si une tâche est en attente dans la file des éligibles, ce
qui n'est pas le cas. Nous allons ensuite vérifier si une tâche
périodique va arriver puis, le cas échéant, dans
combien de temps. Dans notre cas nous avons 2 unités de temps à disposition avant l'arrivée de $T2$.
Il
est alors impossible d'étendre la durée de la tâche $T1$ et nous allons l'exécuter
à la vitesse maximum.
\paragraph{}
Cependant, une fois l'instance de la tâche $T2$ terminée, il nous reste 2 unités de temps à
exécuter pour l'instance de la tâche $T1$. Ayant cette fois-ci un temps à disposition de 4
unités avant l'arrivée de $T5$, il est dès lors possible d'étendre la durée restante de l'instance
de la tâche
$T1$. Pour ce faire, comme vous l'aurez sûrement compris, il est nécessaire de
connaître le temps restant de l'instance de la tâche $T1$. De ce fait, il faut aussi
ajouter le temps d'exécution restant de l'instance d'une tâche dans celle-ci.
\begin{figure}[h!]
\centering
\includegraphics{../Imgs/SchemaTemspRestant.png}
% SchemaTemspRestant.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Extension d'une tâche après réordonnancement}
\end{figure}
\FloatBarrier

Après la démonstration effectuée, voici une ébauche du pseudo-code d'OTE.\\

\begin{lstlisting}[frame=trbl]
A chaque ordonnancement d une tache
	Si la file des taches eligibles est vide
		Si la file des arrivees est vide // cas d'un systeme mono-tache
			Etendre la tache au maximum (jusqu a son echeance)
		Sinon si la file contient au moins une tache
			Reccuperer la tache ayant l heure d arrivee h la plus proche
			Pour tous les facteurs f disponibles, par ordre decroissant
				Si l heure actuel - h >= (f x duree d execution restante)
					Etendre la duree de la tache de f et diminuer la
					frequence et la tension du	processeur selon leurs facteurs
					respectifs
					Sortir de la boucle
			Si aucun facteur n a permis d etendre la duree de la tache tout en respectant son echeance
				Executer la tache avec le processeur a frequence maximum
			Fin si
		Fin si
	Sinon 
		Executer la tache avec le processeur a frequence maximum
	Fin si
\end{lstlisting}

Remarque : \begin{itemize}
\item 
Nous n'entrons pas dans le détail des facteurs puisque ce point a
déjà été abordé en début du chapitre.\\
\item 
Au lieu de tester si aucun facteur n'a été trouvé puis d'exécuter le processeur à sa vitesse
maximum, il aurait été possible de simplifier l'algorithme en ajoutant un facteur de 1
correspondant à la fréquence maximum. Toutefois, dans le cas où le programme n'est pas
ordonnançable,
cette dernière façon de procéder engendrera que le processeur continue à s'exécuter avec la dernière
fréquence qu'on lui a appliqué. Ainsi, même si le programme est sensé être ordonnançable, il est
préférable, en cas d'erreur de l'utilisateur, que le processeur s'exécute à vitesse maximum ce qui
atténuera l'erreur.            
\end{itemize}

\paragraph{}
Dans le prochain chapitre, nous regarderons quel matériel a été utilisé pour effectué le
développement du projet.











